home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
hash.zip
/
LIST.6
< prev
next >
Wrap
Text File
|
1993-01-04
|
4KB
|
93 lines
Program Search_With_Chaining;
Const
max_TAB_entry = 60; {last TAB entry number}
number_TAB_entries = 61; {the number of entries in TAB}
Type
tab_pointer = ^tab_entry; {define a pointer to tab_entry (below)}
string4 = string[4];
tab_entry = record {define an entry of TAB}
KEY_field: string4; {holds KEY for this entry}
CHAIN: tab_pointer; {pointer to next entry with same hash value}
end;
Var
found: boolean; {set true by Search if KEY is found}
index: tab_pointer; {pointer to the current TAB entry being examined}
KEY: string4; {name to be found or entered}
i: integer; {for FOR loop use}
node: array[ 0 .. max_TAB_entry ] of tab_pointer; {heads for each chain}
Procedure Search( KEY: string4 );
Function h( KEY: string4 ): integer;
Type
KEY_types = (char_KEY, integer_KEY);
KEY_overlay = record
case KEY_types of
char_KEY: ( KEY_in_characters: string4 );
integer_KEY: ( dummy: byte; {takes up room for string size}
integer_KEY_1: integer; {first 2 bytes of KEY}
integer_KEY_2: integer; {last 2 bytes of KEY}
);
end;
Var
KEY_record: KEY_overlay;
begin {hash}
with KEY_record do
begin
KEY_in_characters := ' '; {clean out in case KEY < 4 chars}
KEY_in_characters := KEY;
h := ( integer_KEY_1 xor integer_KEY_2 ) mod number_TAB_entries;
end;
end; {hash}
Var
hash: integer; {holds the hash value the current KEY}
last_index: tab_pointer; {points to the last entry examined}
Begin {Search}
found := false;
hash := h( KEY ); {go hash KEY}
index := node[ hash ];
if index = nil then {this is the first KEY with this hash value}
begin
new( index ); {create an entry for it}
node[ hash ] := index; {and set node to point to it}
index^.CHAIN := nil; {mark this entry as the end of the chain}
index^.KEY_field := KEY; {enter KEY into TAB entry}
end
else {there are entries with this hash value - search them}
begin
while ( index <> nil ) and not found do
begin
if index^.KEY_field = KEY then {found it}
found := true
else {point to next entry with this hash value}
begin
last_index := index; {point to the LAST entry}
index := index^.CHAIN;
end;
end;
if not found then {create a new entry}
begin
new( last_index^.chain );
index := last_index^.chain; {and point to it with index}
index^.CHAIN := nil; {mark this entry as end of chain}
index^.KEY_field := KEY; {enter KEY into TAB entry}
end;
end;
end; {Search}
Begin {Search_With_Chaining}
for i:=0 to max_TAB_entry do node[i]:=nil; {set nodes to point nowhere}
{User Code Goes Here}
End. {Search_With_Chaining}